/*
提交链接：https://leetcode.cn/problems/house-robber/description/
198.打家劫舍
刘思琪 2024/9/7
*/

//偷k，则第k-1不偷，此时总金额为k-2的+k的
//不偷k，则总金额为k-1
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> t(nums.size(),0);
        t[0]=nums[0];
        t[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            t[i]=max(t[i-2]+nums[i],t[i-1]);
        }
        return t[nums.size()-1];
    }
};